// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. #nullable enable using System; using System.Collections.Generic; using System.Collections.Immutable; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Threading; using Microsoft.CodeAnalysis.PooledObjects; using Roslyn.Utilities; namespace Microsoft.CodeAnalysis.Shared.Collections { /// <summary> /// Provides temporary storage for a collection of elements. This type is optimized for handling of small /// collections, particularly for cases where the collection will eventually be discarded or used to produce an /// <see cref="ImmutableArray{T}"/>. /// </summary> /// <remarks> /// This type stores small collections on the stack, with the ability to transition to dynamic storage if/when /// larger number of elements are added. /// </remarks> /// <typeparam name="T">The type of elements stored in the collection.</typeparam> [NonCopyable] [StructLayout(LayoutKind.Sequential)] internal struct TemporaryArray<T> : IDisposable { /// <summary> /// The number of elements the temporary can store inline. Storing more than this many elements requires the /// array transition to dynamic storage. /// </summary> private const int InlineCapacity = 4; /// <summary> /// The first inline element. /// </summary> /// <remarks> /// This field is only used when <see cref="_builder"/> is <see langword="null"/>. In other words, this type /// stores elements inline <em>or</em> stores them in <see cref="_builder"/>, but does not use both approaches /// at the same time. /// </remarks> private T _item0; /// <summary> /// The second inline element. /// </summary> /// <seealso cref="_item0"/> private T _item1; /// <summary> /// The third inline element. /// </summary> /// <seealso cref="_item0"/> private T _item2; /// <summary> /// The fourth inline element. /// </summary> /// <seealso cref="_item0"/> private T _item3; /// <summary> /// The number of inline elements held in the array. This value is only used when <see cref="_builder"/> is /// <see langword="null"/>. /// </summary> private int _count; /// <summary> /// A builder used for dynamic storage of collections that may exceed the limit for inline elements. /// </summary> /// <remarks> /// This field is initialized to non-<see langword="null"/> the first time the <see cref="TemporaryArray{T}"/> /// needs to store more than four elements. From that point, <see cref="_builder"/> is used instead of inline /// elements, even if items are removed to make the result smaller than four elements. /// </remarks> private ArrayBuilder<T>? _builder; private TemporaryArray(in TemporaryArray<T> array) { // Intentional copy used for creating an enumerator #pragma warning disable RS0042 // Do not copy value this = array; #pragma warning restore RS0042 // Do not copy value } public static TemporaryArray<T> GetInstance(int capacity) { // Capacity <= 4 is already supported by the Empty array value. so can just return that without allocating anything. if (capacity <= InlineCapacity) return Empty; return new TemporaryArray<T>() { _builder = ArrayBuilder<T>.GetInstance(capacity) }; } public static TemporaryArray<T> Empty => default; public readonly int Count => _builder?.Count ?? _count; public T this[int index] { [MethodImpl(MethodImplOptions.AggressiveInlining)] readonly get { if (_builder is not null) return _builder[index]; if ((uint)index >= _count) ThrowIndexOutOfRangeException(); return index switch { 0 => _item0, 1 => _item1, 2 => _item2, _ => _item3, }; } [MethodImpl(MethodImplOptions.AggressiveInlining)] set { if (_builder is not null) { _builder[index] = value; return; } if ((uint)index >= _count) ThrowIndexOutOfRangeException(); _ = index switch { 0 => _item0 = value, 1 => _item1 = value, 2 => _item2 = value, _ => _item3 = value, }; } } public void Dispose() { // Return _builder to the pool if necessary. There is no need to release inline storage since the majority // case for this type is stack-allocated storage and the GC is already able to reclaim objects from the // stack after the last use of a reference to them. Interlocked.Exchange(ref _builder, null)?.Free(); } public void Add(T item) { if (_builder is not null) { _builder.Add(item); } else if (_count < InlineCapacity) { // Increase _count before assigning a value since the indexer has a bounds check. _count++; this[_count - 1] = item; } else { Debug.Assert(_count == InlineCapacity); MoveInlineToBuilder(); _builder.Add(item); } } public void AddRange(ImmutableArray<T> items) { if (_builder is not null) { _builder.AddRange(items); } else if (_count + items.Length <= InlineCapacity) { foreach (var item in items) { // Increase _count before assigning values since the indexer has a bounds check. _count++; this[_count - 1] = item; } } else { MoveInlineToBuilder(); _builder.AddRange(items); } } public void AddRange(in TemporaryArray<T> items) { if (_count + items.Count <= InlineCapacity) { foreach (var item in items) { // Increase _count before assigning values since the indexer has a bounds check. _count++; this[_count - 1] = item; } } else { MoveInlineToBuilder(); foreach (var item in items) _builder.Add(item); } } public void Clear() { if (_builder is not null) { // Keep using a builder even if we now fit in inline storage to avoid churn in the object pools. _builder.Clear(); } else { this = Empty; } } public T RemoveLast() { var count = this.Count; var last = this[count - 1]; this[count - 1] = default!; if (_builder != null) { _builder.Count--; } else { _count--; } return last; } public readonly bool Contains(T value, IEqualityComparer<T>? equalityComparer = null) => IndexOf(value, equalityComparer) >= 0; public readonly int IndexOf(T value, IEqualityComparer<T>? equalityComparer = null) { equalityComparer ??= EqualityComparer<T>.Default; if (_builder != null) return _builder.IndexOf(value, equalityComparer); var index = 0; foreach (var v in this) { if (equalityComparer.Equals(v, value)) return index; index++; } return -1; } public readonly Enumerator GetEnumerator() { return new Enumerator(in this); } /// <summary> /// Create an <see cref="OneOrMany{T}"/> with the elements currently held in the temporary array, and clear the /// array. /// </summary> public OneOrMany<T> ToOneOrManyAndClear() { switch (this.Count) { case 0: return OneOrMany<T>.Empty; case 1: var result = OneOrMany.Create(this[0]); this.Clear(); return result; default: return new(this.ToImmutableAndClear()); } } /// <summary> /// Create an <see cref="ImmutableArray{T}"/> with the elements currently held in the temporary array, and clear /// the array. /// </summary> public ImmutableArray<T> ToImmutableAndClear() { if (_builder is not null) { return _builder.ToImmutableAndClear(); } else { var result = _count switch { 0 => ImmutableArray<T>.Empty, 1 => ImmutableArray.Create(_item0), 2 => ImmutableArray.Create(_item0, _item1), 3 => ImmutableArray.Create(_item0, _item1, _item2), 4 => ImmutableArray.Create(_item0, _item1, _item2, _item3), _ => throw ExceptionUtilities.Unreachable(), }; // Since _builder is null on this path, we can overwrite the whole structure to Empty to reset all // inline elements to their default value and the _count to 0. this = Empty; return result; } } /// <summary> /// Transitions the current <see cref="TemporaryArray{T}"/> from inline storage to dynamic storage storage. An /// <see cref="ArrayBuilder{T}"/> instance is taken from the shared pool, and all elements currently in inline /// storage are added to it. After this point, dynamic storage will be used instead of inline storage. /// </summary> [MemberNotNull(nameof(_builder))] private void MoveInlineToBuilder() { Debug.Assert(_builder is null); var builder = ArrayBuilder<T>.GetInstance(); for (var i = 0; i < _count; i++) { builder.Add(this[i]); #if NET if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) #endif { this[i] = default!; } } _count = 0; _builder = builder; } public void ReverseContents() { if (_builder is not null) { _builder.ReverseContents(); return; } switch (_count) { case <= 1: // if we have one or zero items, we're already reversed. return; case 2: (_item0, _item1) = (_item1, _item0); return; case 3: // Just need to swap the first and last items. The middle one stays where it is. (_item0, _item2) = (_item2, _item0); return; case 4: (_item0, _item1, _item2, _item3) = (_item3, _item2, _item1, _item0); return; default: throw ExceptionUtilities.Unreachable(); } } public void Sort(Comparison<T> compare) { if (_builder is not null) { _builder.Sort(compare); return; } switch (_count) { case <= 1: return; case 2: if (compare(_item0, _item1) > 0) { (_item0, _item1) = (_item1, _item0); } return; case 3: if (compare(_item0, _item1) > 0) (_item0, _item1) = (_item1, _item0); if (compare(_item1, _item2) > 0) { (_item1, _item2) = (_item2, _item1); if (compare(_item0, _item1) > 0) (_item0, _item1) = (_item1, _item0); } return; case 4: if (compare(_item0, _item1) > 0) (_item0, _item1) = (_item1, _item0); if (compare(_item2, _item3) > 0) (_item2, _item3) = (_item3, _item2); if (compare(_item0, _item2) > 0) (_item0, _item2) = (_item2, _item0); if (compare(_item1, _item3) > 0) (_item1, _item3) = (_item3, _item1); if (compare(_item1, _item2) > 0) (_item1, _item2) = (_item2, _item1); return; default: throw ExceptionUtilities.Unreachable(); } } /// <summary> /// Throws <see cref="IndexOutOfRangeException"/>. /// </summary> /// <remarks> /// This helper improves the ability of the JIT to inline callers. /// </remarks> private static void ThrowIndexOutOfRangeException() => throw new IndexOutOfRangeException(); [NonCopyable] public struct Enumerator { private readonly TemporaryArray<T> _array; private T _current; private int _nextIndex; public Enumerator(in TemporaryArray<T> array) { // Enumerate a copy of the original _array = new TemporaryArray<T>(in array); _current = default!; _nextIndex = 0; } public T Current => _current; public bool MoveNext() { if (_nextIndex >= _array.Count) { return false; } else { _current = _array[_nextIndex]; _nextIndex++; return true; } } } internal static class TestAccessor { public static int InlineCapacity => TemporaryArray<T>.InlineCapacity; public static bool HasDynamicStorage(in TemporaryArray<T> array) => array._builder is not null; public static int InlineCount(in TemporaryArray<T> array) => array._count; } } } |